#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
class Solution {
public:

    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>>ans;
        int i = 0;
        for (;i<intervals.size();i++)
        {
            if (intervals[i][0] > newInterval[0])break;
            ans.push_back(intervals[i]);
        }

        if (ans.empty() || ans.back()[1] < newInterval[0])ans.push_back(newInterval);
        else ans.back()[1] = newInterval[1] > ans.back()[1] ? newInterval[1] : ans.back()[1];

        for (; i < intervals.size(); i++)
        {
            if (ans.empty() || ans.back()[1] < intervals[i][0])break;
            else ans.back()[1] = intervals[i][1] > ans.back()[1] ? intervals[i][1] : ans.back()[1];
        }
        for (; i < intervals.size(); i++)
        {
            ans.push_back(intervals[i]);
        }
        return ans;
    }

};